#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE

	};

	template<class K, class V>
	struct HashData
	{
        public:
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv) {
            if(_n * 10 / _tables.size() >= 7) {
                _Resize();
            }
            Hash h;
            size_t hk = h(kv.first) % _tables.size();
            size_t index = hk;
            size_t i = 0;
            while (true) {
                if(_tables[index]._state == EMPTY || _tables[index]._state == DELETE) {
                    _tables[index]._kv = kv;
                    _tables[index]._state = EXIST;
                    return true;
                }else if(_tables[index]._state == EXIST && _tables[index]._kv.first == kv.first) {
                    _tables[index]._kv.second = kv.second;
                    return true;
                }
                index = (hk + (++i)) % _tables.size();
                if(i >= _tables.size()) {
                    return false;
                }
            }
        }
		HashData<K, V>* Find(const K& key) {
            Hash h;
            size_t hk = h(key) % _tables.size();
            size_t index = hk;
            size_t i = 0;
            while(_tables[index]._state != EMPTY) {
                if(_tables[index]._state == EXIST && _tables[index]._kv.first == key) {
                    return &_tables[index];
                }
                index = (hk + (++i)) % _tables.size();
                if(i >= _tables.size()) {
                    return nullptr;
                }
            }
            return nullptr;
        }   
		bool Erase(const K& key) {
            auto index = Find(key);
            if(index) {
                index->_state = DELETE;
                _n--;
                return true;
            }else {
                return false;
            }
        }
        void Print() {
            cout << "哈希表中的内容如下：" << endl;
            for(int i = 0; i < _tables.size(); i++) {
                if(_tables[i]._state == EXIST) {
                    cout << "[" << i << "]" << _tables[i]._kv.first << " : " << _tables[i]._kv.second << endl;
                }else {
                    cout << "[" << i << "]" << "EMPTY" << endl;
                }
            }
            cout << endl;
        }
    private:
        void _Resize() {
            vector<HashData<K, V>> temp = _tables;
            _tables.clear();
            temp.resize(temp.size() * 2);
            _n = 0;
            for(auto& e : temp) {
                if(e._state == EXIST) {
                    Insert(e._kv);
                }
            }
        }
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}


// 实现完成后，请对整形 和 字符串完成测试


// 测试代码
int main()
{
    using namespace open_address;

    cout << "===== 整型哈希表测试 =====" << endl;
    HashTable<int, string> ht1;
    ht1.Insert({1, "one"});
    ht1.Insert({11, "eleven"});
    ht1.Insert({21, "twenty-one"});
    ht1.Insert({2, "two"});
    ht1.Print();

    auto f1 = ht1.Find(11);
    if (f1) cout << "找到 key=11, value=" << f1->_kv.second << endl;

    ht1.Erase(11);
    ht1.Print();

    cout << "\n===== 字符串哈希表测试 =====" << endl;
    HashTable<string, int> ht2;
    ht2.Insert({"apple", 100});
    ht2.Insert({"banana", 200});
    ht2.Insert({"orange", 300});
    ht2.Print();

    auto f2 = ht2.Find("banana");
    if (f2) cout << "找到 key='banana', value=" << f2->_kv.second << endl;

    ht2.Erase("banana");
    ht2.Print();

    return 0;
}